perm filename ANA1[NCC,BGB] blob
sn#143276 filedate 1975-02-04 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {F1F2F3⊂C<NαWINGED EDGE.λ30P1I125,0JCFA}
C00005 00003 ⊂0. Introduction to the Winged Edge.⊃
C00007 00004 {H7O0,630,700
C00009 00005 ⊂1. Winged Edge Link Fields.⊃
C00013 00006
C00017 00007 {QP6}⊂2. Sequential Accessing.⊃
C00020 00008 ⊂3. Perimeter Accessing.⊃
C00028 00009 ⊂4. Basic Polyhedron Synthesis.⊃
C00030 00010 <Node Makers and Killers>. The MKNODE and KLNODE are the raw
C00032 00011 <Wing Mungers>. The WING(edge1,edge2) routine finds which
C00035 00012 <Part Tree Routines>. As mentioned before, body nodes can be
C00037 00013 ⊂5. Edge and Face Splitting.⊃
C00043 00014 {O0,0,450L0,255FCJC} FIGURE 3 - ESPLIT AND KLEV.{
C00048 00015 {O0,630,450L0,255FCJC} FIGURE 4 - MKFE AND KLFE.{
C00064 ENDMK
C⊗;
{F1;F2;F3;⊂C;<N;αWINGED EDGE.;λ30;P1;I125,0;JC;FA}
{JC;FD} A POLYHEDRON REPRESENTATION FOR COMPUTER VISION
{λ15;FA} Author: {JCFC} Bruce G. Baumgart
{FA} Author's Address: {JC} Stanford Artificial Intelligence Laboratory
{JC} Stanford University
{JC} Stanford, California 94305
Session chaired by: {JC} Charles M. Eastman
Old Session title: {JC} Database Developments in Interactive Graphics
New Session title: {JC} Graphic Models of Physical Systems
{λ10;W250;JA;FA}
0. Introduction to the Winged Edge.
1. Winged Edge Link Fields.
2. Sequential Accessing.
3. Perimeter Accessing.
4. Basic Polyhedron Synthesis.
5. Edge and Face Splitting.
6. Coordinate Free Polyhedron Representation.
7. Use of Polyhedra in Computer Vision.
8. References.
{λ30;W0;I1000,0;JU}
⊂0. Introduction to the Winged Edge.⊃
The remainder
bulk of this paper is a detailed presentation
of a particular representation for polyhedra.
The representation is implemented as a data structure composed of small
blocks of words containing pointers and data in the fashion usual to
graphics and simulation. An introduction to such data structures can
be found in Chapter 2 of Knuth's Art of Computer Programming [Knuth 1968].
Quickly reviewing Knuth's terminology, a node is a group of
consecutive words of memory, a field is a named portion of a node
and a link is the machine address of a node. The notation for
referring to a field of a node consists simply of the field name
followed by a link expression enclosed in parentheses. For example,
the two faces of an edge node whose link is stored in the variable
named "edge", are found in the fields named NFACE and PFACE, and are
referred to as NFACE(edge) and PFACE(edge). Although my latest
language of implementation is PDP-10 machine code, examples will
be given in a fictional programming language which combines ALGOL
with Knuth's node/link notation.
{H7;O0,630,700;
L0,-20,0*5,-61*5;L0,20,0*5,61*5;
L-86*5,83*5,0*5,61*5,86*5,83*5;L-86*5,-83*5,0*5,-61*5,86*5,-83*5;
H2;
L42*5,106*5,86*5,83*5,126*5,0*5,86*5,-83*5,42*5,-106*5,-42*5,-106*5;
L-42*5,-106*5,-86*5,-83*5,-126*5,0*5,-86*5,83*5,-42*5,106*5,42*5,106*5;
L-30,-10;FB }edge
{L-380,-10; }NFACE(edge)
{L240,-10; }PFACE(edge)
{L-70,-370; }NVT(edge)
{L-70,350; }PVT(edge)
{L-360,320; }NCCW(edge)
{L-390,-360; }NCW(edge)
{L220,320; }PCW(edge)
{L260,-360; }PCCW(edge)
{I1300,0;O0,630,950;
λ10;JC;FA} ⊂FIGURE 1 - Winged Edge Topology.⊃
The orientation of links is as viewed from the exterior side of the surface.
The eight mnemonics in the figure, were derived as follows:
NFACE(edge) Negative Face of edge.
PFACE(edge) Positive Face of edge.
PVT(edge) Positive Vertex of edge.
NVT(edge) Negative Vertex of edge.
NCW(edge) edge in Negative face Clockwise from edge.
PCW(edge) edge in Positive face Clockwise from edge.
NCCW(edge) edge in Negative face Counter Clockwise from edge.
PCCW(edge) edge in Positive face Counter Clockwise from edge.{λ30;FA}
{Q}
⊂1. Winged Edge Link Fields.⊃
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. In this
context, a ring is a doubly linked circular list with a head node.
Each face and each vertex points directly at only one of the edges on
its perimeter. Each edge points at its two faces and its two
vertices. Completing the topology, each edge node contains a link to
each of its four immediate neighboring edges clockwise and counter
clockwise about its face perimeters as seen from the exterior side of
the surface of the polyhedron. These last four links are the wings of
the edge, which provide the basis for efficient face perimeter and
vertex perimeter accessing. Finally, the links of the edge nodes
can be consistently oriented with respect to the surface of the
polyhedron so that the surface always has two sides: the inside and
the outside.
{|;λ10;JA}
BOX 1 {JC} WINGED EDGE STRUCTURES AND LINK NAMES.
~Data Structures~ ~Link Names~
1. Face Ring of a Body. NFACE PFACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW NCCW PCCW
{|;λ30;JU}
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. If we allow a link name such as PED
to serve different roles depending on whether it applies to a body,
face, edge or vertex; then the minimum number of different link field
names that need to be coined is ten. The data structures and the link
fields comprising the structures are listed in Box 1. The
ten link names include: NFACE and PFACE for two fields that contain
face links in edges and the face ring, NED and PED for two fields
that contain edge links, NVT and PVT for two fields that contain
vertex links, and NCW, PCW, NCCW and PCCW for the four fields that
contain edge links and are called the wings.
By constraining the arrangement of links in an edge node both
the surface orientation (interior and exterior) and a linear
orientation of the edge as a directed vector can be encoded. Figure
1 diagrams the arrangement of the links comprising the topology of
an edge of a polyhedron as viewed from the exterior side of its
surface. Although the vertices in Figure 1 are shown with only
three edges, vertices may have any number of edges; the other
potential edges would not be directly linked to the middle edge of
the figure and so were not shown.
To complete the representation, space is allocated to contain
the 3-D coordinates of each vertex in fields named XWC, YWC and ZWC;
the initials "WC" stand for <World Coordinates>. For the sake of
vision and display, three more words are allocated to hold
the <Perspective Projected coordinates> of each vertex in fields
named XPP, YPP and ZPP. Also a word of thirty six status bits is
carried in every node: permanent status bits specify the type (body,
face, edge, vertex, etc.) of every node, temporary bits provide
space for operations such as hidden line elimination that require
marking. Passing now from necessities to conveniences, faces carry
exterior pointing normal vectors and several words of photometric
surface characteristics. The face vectors are derived from surface
topology and vertex loci, and so they are not basic geometric data
as in some representations. Bodies carry a print name, as well as
four link fields (DAD, SON, BRO, SIS) for implementing a parts tree
data structure; and two link fields (CW and CCW) for a body ring of
all the bodies in the world model. Node formats are given in Box 2
for an implementation based on fixed sized (twelve word) nodes.
The Winged Edge Polyhedron Representation as just presented
is complete. Edge nodes carry most of the topology, vertex nodes
carry the geometry, face nodes carry the photometry and body nodes
carry the nomenclature and parts tree structure. The
point that remains to be demonstrated, is that the appropriate
subroutines for creating, maintaining and exploiting edge
orientation execute efficiently and provide good primitives for
solving such geometric problems as hidden line elimination and
polyhedral intersection.
{Q;P6;}⊂2. Sequential Accessing.⊃
An immediate consequence of the ring structures is that the
faces, edges and vertices of a body are sequentially accessible in the
manner illustrated by the following lines of code:
{JA;W0;λ7;F3}
COMMENT APPLY A FUNCTION TO ALL THE FACES, EDGES AND VERTICES OF A BODY;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
INTEGER F,E,V;
F ← B; WHILE B≠(F←PFACE(F)) DO FN(F); COMMENT APPLY FUNCTION TO FACES OF A BODY;
E ← B; WHILE B≠(E←PED(E)) DO FN(E); COMMENT APPLY FUNCTION TO EDGES OF A BODY;
V ← B; WHILE B≠(V←PVT(V)) DO FN(V); COMMENT APPLY FUNCTION TO VERTICES OF A BODY;
END;
{JUFA;W0;λ30;}
\The rings could of course have been traversed in the other direction by
invoking NVT, NED and NFACE in place of PVT, PED and PFACE. The reason
for doubly linked lists (i.e. rings) is rapid deletion. Finally, observe
that the face and vertex rings could be eliminated at the cost of having
a more complicated face/vertex sequential accessing method requiring a
visitation marking bit in the status word of face and vertex nodes.
The idea might be coded as follows:
{JA;W100;λ7;F3;}
COMMENT APPLY A FUNCTION TO ALL THE FACES OF A BODY WITHOUT USING THE FACE RINGS;
PROCEDURE APPLY (PROCEDURE FN; INTEGER B);
BEGIN
INTEGER F,E,M;
E ← B; COMMENT FIRST EDGE OF BODY;
M ← MARK(PFACE(E)); COMMENT READ INITIAL STATE OF MARKING BIT;
DO FOR F ← PFACE(E),NFACE(E) DO COMMENT FOR BOTH FACES OF EACH EDGE...;
BEGIN
IF M=MARK(F) THEN FN(F); COMMENT APPLY FUNCTION TO "UN-RE-MARKED" FACE;
MARK(F) ← ¬M; COMMENT FLIP THE MARKING BIT;
END;
UNTIL B=(E←PED(E)); COMMENT ALL THE EDGES OF THE BODY;
END;
{JUFA;W0;λ30;}
⊂3. Perimeter Accessing.⊃
The perimeter of a face is an ordered list of edges and
vertices, the perimeter of a vertex is an ordered list of edges and
faces, and the perimeter of an edge is an ordered list consisting of
exactly two faces and two vertices. The perimeter definitions are
caricatured in Figure 2. One virtue of the winged edge
representation is that both vertex and face perimeters can be
traversed in either direction (clockwise or counter clockwise) while
being dynamically maintained in "<one ring>".
{O0,630,350;L0,0;H3;FD
L0,-137;C6;L0,-137,0,170;C6;
L-44,10;FD}EDGE{
L-125,-170;FA}An Edge is surrounded{
L-120,-200;FA}by Faces and Vertices{
L0,200;JC;FC} FIGURE 2 - Three Kinds of Perimeters.{
L420,170,420-161,52;C6;
L420-161,52,420-100,-137;C6;
L420-100,-137,420+100,-137;C6;
L420+100,-137,420+161,52;C6;
L420+161,52,420,170;C6;
L420-45,-10;FD}FACE{
L420-125,-170;FA}A Face is surrounded{
L420-130,-200;FA}by Edges and Vertices{
L-420,0,-420-161,52;
L-420,0,-420-100,-137;
L-420,0,-420+100,-137;
L-420,0,-420+161,52;
L-420,170,-420,0;C6;
L-420-70,30;FD}VERTEX{
L-420-125,-170;FA}A Vertex is surrounded{
L-420-115,-200;FA}by Edges and Faces{O0,630,950;I590,0;JUFA}
Given one edge of a face (or vertex) perimeter, the next
edge clockwise (or counter clockwise) from the given edge about the
particular face (or vertex) can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face (or vertex)
with one of the faces (or vertices) of the given edge and to then
return the appropriate wing. A possible coding of ECCW and ECW might
be as follows:
{↓;JA;λ7;F3}
COMMENT FETCH EDGE CCW FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
{↑;W670;JA;λ7;F3}
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
{W0;JUFA;λ30;}
\The first edge of a face or vertex is (of course) immediately
available from the PED field of the face or vertex. For example, the
two procedures below can be used to visit all the edges of a face or
all the edges of a vertex, respectively.
{JA;↓;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A FACE;
PROCEDURE APPLY (PROCEDURE FN; INTEGER F);
BEGIN
INTEGER E,E0;
E←E0←PED(F);
DO FN(E) UNTIL E0=(E←ECCW(E,F));
END;
{↑;W670;JA;λ7;F3}
COMMENT APPLY FUNCTION TO EDGES OF A VERTEX;
PROCEDURE APPLY (PROCEDURE FN; INTEGER V);
BEGIN
INTEGER E,E0;
E←E0←PED(V);
DO FN(E) UNTIL E0=(E←ECCW(E,V));
END;
{JUFA;W0;λ30;}
Using the same idea as in the edge clocking routines, a face
or vertex can be retrieved relative to a given edge and a given face
or vertex. These routines include: FCW and FCCW which return the face
clockwise or counter clockwise from a given edge with respect to a
given vertex; VCW and VCCW which return the vertex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which returns the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to ever explicitly
reference a wing field when traveling the surface of a polyhedron.
With node type checking the primitives can be made stronger, for example
ECCW(vertex,face) is implemented to return the edge counter clockwise
from the given vertex about the given face.
With node type checking and signed arguments the seven perimeter
accessing routines could even be replaced by a single routine perhaps
named PERIMETER_FETCH or PGET. On the other hand, I favor having the
proliferation of accessing names for the sake of documenting the
clocking direction and the types of nodes involved.
Two remaining accessing routines, of minor importance,
are BGET(entity) and LINKED(entity,entity). BGET of a face, edge or
vertex merely cycles the appropriate ring to retrieve the body of the
given entity. The LINKED routine determines whether its two
arguments (faces, edges or vertices) are adjacent; there are six
LINKED cases: (i) Face-Face, returns a common edge or FALSE; (ii)
Face-Edge, returns boolean value F=PFACE(E) ∨ F=NFACE(E); (iii)
Edge-Edge, returns a common vertex or false; (v) Edge-Vertex,
returns boolean value V=PVT(E) ∨ V=NVT(E); (vi) Vertex-Vertex,
returns common edge or FALSE. (As in LISP, zero is false and non-zero
is true).
⊂4. Basic Polyhedron Synthesis.⊃
{|;λ10;JA}
BOX 3 {JC} LOWEST LEVEL WINGED EDGE ROUTINES.
<Node Makers:> MKNODE, MKB, MKF, MKE, MKV, MKTRAM.
<Node Killers:> KLNODE, KLB, KLF, KLE, KLV.
<Wing Mungers:> WING, INVERT, EVERT.
<Surface Fetchers:> ECW, ECCW, OTHER, VCW, VCCW, FCW, FCCW, LINKED.
<Parts Tree Routines:> BDET, BATT, BGET.
{|;λ30;JU}
There are sixteen routines for node creation and link
manipulation which when combined with the nine accessing routines of
the previous section form the nucleus of a polyhedron modeling
system. These routines are very low level in that the final
applications user of winged polyhedra will never explicitly need to
make a node or mung a link. The word <mung> (meaning to modify an
existing structure by altering links in place) is LISP slang that
deserves to be promoted into the technical jargon; traditionally, a
mung routine is one which makes applications of the LISP primitives
RPLACA and RPLACD. The twenty five routines listed in Box 3 are
the bedrock foundation for the Euler primitives presented in section 3
of [Baumgart 1974B].
<Node Makers and Killers>. The MKNODE and KLNODE are the raw
storage allocation routines which fetch or return a node from the
available free storage. The MKB routine creates a body node with
empty face, edge and vertex rings; the body is placed into the body
ring of the world model. The MKF, MKE and MKV each take one
argument and create a new face, edge or vertex node in the ring of
the given entity; with type checking these three primitives could be
consolidated. Finally the MKTRAM node creates a <tram node>, which
consists of twelve real numbers that represent either a Euclidean
transformation or a Cartesian frame of reference depending on the
context. Tram nodes are explained in [Baumgart 1974B].
The corresponding kill routines KLB, KLF, KLE and
KLV remove the entity from its respective ring and return its node to
free storage.
<Wing Mungers>. The WING(edge1,edge2) routine finds which
face and vertex the arguments edge1 and edge2 have in common and
stores the wing pointers between edge1 and edge2 accordingly; the
exact link manipulations are illustrated in the example coding of
the WING procedure immediately following this paragraph. Recalling
that edges are directed vectors, the INVERT(E) routine flips the
direction of an edge by swapping the contents of the appropriate
fields as follows: PFACE(E)↔NFACE(E); PVT(E)↔NVT(E); NCW(E)↔NCCW(E)
and PCW(E)↔PCCW(E). Finally, the EVERT(B) routine
turns a body inside out, by
performing the following link swaps on all the edges of the given body:
PFACE(E)↔NFACE(E); NCW(E)↔PCCW(E); and NCCW(E)↔PCW(E).
{JA;λ7;F3;W120,1260,0,1900;}
PROCEDURE WING(INTEGER E1,E2);
BEGIN
IF PVT(E1)=PVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCW(E1)←E2;NCCW(E2)←E1;END;
IF PVT(E1)=PVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCCW(E1)←E2; PCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCW(E1)←E2;PCCW(E2)←E1;END;
IF PVT(E1)=NVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧PFACE(E1)=PFACE(E2)THEN BEGIN PCCW(E1)←E2; PCW(E2)←E1;END;
IF NVT(E1)=PVT(E2)∧NFACE(E1)=NFACE(E2)THEN BEGIN NCW(E1)←E2;NCCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧PFACE(E1)=NFACE(E2)THEN BEGIN PCCW(E1)←E2; NCW(E2)←E1;END;
IF NVT(E1)=NVT(E2)∧NFACE(E1)=PFACE(E2)THEN BEGIN NCW(E1)←E2;PCCW(E2)←E1;END;
END;{λ30;W0,1260,150,1800;JUFA}
<Part Tree Routines>. As mentioned before, body nodes can be
grouped into a tree structure of parts. The parts tree consumes four
link positions (DAD, SON, BRO, SIS) and is maintained in body
nodes by the following primitives: BDET(body) detachs a body node
from the parts tree, BATT(body1,body2) attachs body1 to the ring of
children belonging to body2, and BGET(entity) returns the body node
at the head of the given face, edge or vertex ring. The SON field of a
body may contain a pointer to a headless ring of subpart bodies, the
ring of subparts is maintained in the BRO (brother) and SIS (sister)
fields, and each subpart contains a pointer back to its parent
in its DAD field. At present, the notion of a body is coincident with
the notion of a connected polyhedron; however by allowing several
bodies to be associated with a single polyhedral surface, a flexible
object such as an animal could be represented.
⊂5. Edge and Face Splitting.⊃
One of the most important properties of the winged edge
representation is that edges and faces can be split using subroutines
that make only local alterations to the data structure; and the
splits can easily be removed (since the doubly linked rings allow
rapid deletion of nodes from a body). The edge split routine, ESPLIT,
makes a new edge and a new vertex and places them into the surface
topology as shown in Figure 3; the kill edge-vertex routine, KLEV,
undoes an ESPLIT. The face split routine, MKFE, creates a new edge
and a new face and places them into the surface topology as shown in
Figure 4; the kill face-edge routine, KLFE, undoes a MKFE.
The rest of this section concerns implementation; it may
be skipped by the applications oriented reader. The split and kill
routines are examples of a pattern which applies to the coding of
operators that alter winged edge structures. In a typical situation,
there are five steps: first, get the proper kinds of nodes into the
body rings using the MKF, MKE, MKV primitives; second, position the
vertices by setting their XWC, YWC, ZWC fields; third, connect each
vertex and face to one of its edges by setting face/vertex PED
fields; fourth, connect each edge to its two faces and its two
vertices by setting the NFACE, PFACE, NVT, PVT fields of the edge;
finally, set up the wing perimeter pointers by applying the WING
primitive to the pairs of edges to be mated.{Q}
{O0,0,450;L0,255;FCJC} FIGURE 3 - ESPLIT AND KLEV.{
O0,630-300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: VNEW ← ESPLIT(EDGE);{
L-200,-270;}AFTER: EDGE ← KLEV(VNEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6; L0,0,0,122;I∂2,∂2;C6;L2,2;C6;
L-20,-160;FA}NVT{
L-20,140;FA}PVT{
L15,-7;FA}VNEW{
L15,50;FA}ENEW{
L15,-75;FA}EDGE{
L-200,-12;}NFACE{
L140,-12;}PFACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: EDGE ← KLEV(VNEW);{
L-200,-240;}AFTER: VNEW ← ESPLIT(EDGE);{
O0,630,950;
JA;I800,0;↓;λ10;F3}
INTEGER PROCEDURE ESPLIT (INTEGER EDGE);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW;
COMMENT CREATE A NEW EDGE AND VERTEX;
VNEW ← MKV(PVT(EDGE));
ENEW ← MKE(EDGE);
COMMENT CONNECT VERTICES & FACES TO EDGES;
PVT(ENEW) ← PVT(EDGE);
NVT(ENEW) ← VNEW;
PVT(EDGE) ← VNEW;
PFACE(ENEW) ← PFACE(EDGE);
NFACE(ENEW) ← NFACE(EDGE);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(PVT(EDGE)=EDGE THEN
PED(PVT(EDGE))←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← EDGE; PCCW(ENEW) ← EDGE;
PCW(EDGE) ← ENEW; PCCW(EDGE) ← ENEW;
WING(NCCW(EDGE),ENEW);
WING(PCW(EDGE),ENEW);
RETURN(VNEW);
END "ESPLIT";
{JA;↑;W620;λ10;F3}
INTEGER PROCEDURE KLEV (INTEGER VNEW);
BEGIN "KLEV"
INTEGER EDGE,ENEW,V,F,B;
ENEW ← PED(VNEW);
EDGE ← ECCW(ENEW,VNEW);
COMMENT ORIENT EDGES AS IN DIAGRAM;
IF NVT(ENEW) ≠ VNEW THEN INVERT(ENEW);
IF PVT(EDGE) ≠ VNEW THEN INVERT(EDGE);
COMMENT TIE E TO ITS NEW UPPER VERTEX AND WINGS;
V ← PVT(EDGE) ← PVT(ENEW);
WING(PCW(ENEW),EDGE);
WING(NCCW(ENEW),EDGE);
COMMENT ELIMINATE OCCURRENCES OF ENEW IN F AND V;
IF PED(V)=ENEW THEN PED(V) ← EDGE
IF PED(PFACE(EDGE))=ENEW THEN
PED(PFACE(EDGE))←EDGE;
IF PED(NFACE(EDGE))=ENEW THEN
PED(NFACE(EDGE))←EDGE;
COMMENT REMOVE NODES FROM RINGS AND RETURN EDGE;
KLV(VNEW);
KLE(ENEW);
RETURN(EDGE);
END "KLEV";
{W0,1260;λ30;JUFA}
The actual routines differ slightly from those given above in
that they do argument type checking and data structure checking;
nevertheless, a diagnostic trace of the implemented version reveals
that the ESPLIT routine executes an average of 170 PDP-10 instructions
and the KLEV routine executes an average of 200 instructions.
{O0,630,450;L0,255;FCJC} FIGURE 4 - MKFE AND KLFE.{
O0,630-300,450;H4;L2,-120;C6;L2,124;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-7;FA}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-240;}BEFORE: ENEW ← MKFE(V1,FACE,V2);{
L-200,-270;}AFTER: FACE ← KLFE(ENEW);{
O0,630+300,450;H4;
L0,0,0,-122;I∂2,∂2;C6;L0,0,0,122;I∂2,∂2;C6;
L-15,-160;FA}V2{
L-15,140;FA}V1{
L-20,-190;FA}NVT{
L-20,170;FA}PVT{
L15,-7;FA}ENEW{
L-200,15;}NFACE{
L-200,-25;}FNEW{
L140,15;}PFACE{
L140,-25;}FACE{
L-172,166,0,122,172,166; L-172,-166,0,-122,172,-166; H2;
L84,212, 172,166,252,0,172,-166,84,-212,-84,-212;
L-84,-212,-172,-166,-252,0,-172,166,-84,212,84,212;
L-200,-270;}BEFORE: FACE ← KLFE(ENEW);{
L-200,-240;}AFTER: ENEW ← MKFE(V1,FACE,V2);{
O0,630,950;JA;λ10;I800,0;↓;F3}
INTEGER PROCEDURE MKFE(INTEGER V1,FACE,V2);
BEGIN "MKFE"
INTEGER V1,V2,FNEW,ENEW,E,E0,B,V;
COMMENT CREATE NEW FACE & EDGE;
FNEW ← MKF(FACE); ENEW ← MKE(PED(FACE));
COMMENT LINK NEW EDGES TO ITS FACES & VERTICES;
PED(F) ← PED(FNEW) ← ENEW;
PFACE(ENEW) ← F; NFACE(ENEW) ← FNEW;
PVT(ENEW) ← V1; NVT(ENEW) ← V2;
COMMENT GET THE WINGS OF THE NEW EDGE;
E2 ← PED(V1);
DO E2←ECW((E1←E2),V1) UNTIL FCW(E1,V1)=FACE;
E4 ← PED(V1);
DO E4←ECW((E3←E4),V2) UNTIL FCW(E3,V2)=FACE;
COMMENT SCAN CCW FROM V1 REPLACING F'S WITH FNEW;
E ← E2;
DO IF PFACE(E)=FACE THEN PFACE(E)←FNEW
ELSE NFACE(E)←FNEW;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK THE WINGS;
WING(E1,ENEW); WING(E2,ENEW);
WING(E3,ENEW); WING(E4,ENEW);
RETURN(ENEW);
END;
{JA;↑;W635;λ10;F3}
INTEGER PROCEDURE KLFE (INTEGER ENEW);
BEGIN "KLFE"
INTEGER FNEW,FACE,V1,V2,E,E1,E2,E3,E4;
COMMENT PICKUP ALL THE LINKS OF ENEW;
FACE ← PFACE(ENEW); FNEW ← NFACE(ENEW);
V1 ← PVT(ENEW); V2 ← NVT(ENEW);
E1 ← PCW(ENEW); E2 ← NCCW(ENEW);
E3 ← NCW(ENEW); E4 ← PCCW(ENEW);
COMMENT GET ENEW LINKS OUT OF FACE, V1 AND V2;
IF PED(V1) = ENEW THEN PED(V1) ← E1;
IF PED(V2) = ENEW THEN PED(V2) ← E3;
IF PED(FACE)=ENEW THEN PED(FACE)←E3;
COMMENT GET RID OF FNEW APPEARANCES;
E ← E2;
DO IF PFACE(E)=FNEW THEN PFACE(E)←FACE
ELSE NFACE(E)←FACE;
UNTIL E4 = (E←ECCW(E,FNEW));
COMMENT LINK WINGS TOGETHER ABOUT FACE;
WING(E2,E1);WING(E4,E3);
KLF(FNEW);KLE(ENEW);
RETURN(FACE);
END;
{W0,1260,0,1900;λ30;JUFA}
Again, the actual routines differ from those given above in that
they do argument type checking and data structure checking. The above two routines
typically take about twice as long to execute as the previous pair; notice
that the execution time is dependent on the length of face perimeters,
which are mostly three or four edges long.{W0,1260,0,1900;